package note.sort;

/**
 * @program: LeetCodePractice
 * @description: 插入排序的实现
 * @author: WongKee
 * @create: 2020-08-27 19:21

 适用情况：
 插入排序所需的时间取决于输入中元素的初始顺序。
 对一个很大且其中的元素已经有序（或者接近有序）的数组排序会比对随机顺序的数组或是逆序数组进行排序快的多。

 对于1到N-1之间的而每一个i,将a[i]与a[0]到a[i-1]中比它小的所有元素一次有序地交换。

 **/
public class InsertionSort extends Example {
    @Override
    void sort(Comparable[] a) {
        int N=a.length;
        for(int i=1;i<N;i++){
            for(int j=i;j>0&&less(a[j],a[j-1]);j--){
                exch(a,j,j-1);
            }
        }
    }
}
